package com.sheng.leetcode.year2023.month08.day16;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author by ls
 * @date 2023/8/16
 * <p>
 * 2682. 找出转圈游戏输家<p>
 * <p>
 * n 个朋友在玩游戏。这些朋友坐成一个圈，按 顺时针方向 从 1 到 n 编号。<p>
 * 从第 i 个朋友的位置开始顺时针移动 1 步会到达第 (i + 1) 个朋友的位置（1 <= i < n），<p>
 * 而从第 n 个朋友的位置开始顺时针移动 1 步会回到第 1 个朋友的位置。<p>
 * 游戏规则如下：<p>
 * 第 1 个朋友接球。<p>
 * 接着，第 1 个朋友将球传给距离他顺时针方向 k 步的朋友。<p>
 * 然后，接球的朋友应该把球传给距离他顺时针方向 2 * k 步的朋友。<p>
 * 接着，接球的朋友应该把球传给距离他顺时针方向 3 * k 步的朋友，以此类推。<p>
 * 换句话说，在第 i 轮中持有球的那位朋友需要将球传递给距离他顺时针方向 i * k 步的朋友。<p>
 * 当某个朋友第 2 次接到球时，游戏结束。<p>
 * 在整场游戏中没有接到过球的朋友是 输家 。<p>
 * 给你参与游戏的朋友数量 n 和一个整数 k ，请按升序排列返回包含所有输家编号的数组 answer 作为答案。<p>
 * <p>
 * 示例 1：<p>
 * 输入：n = 5, k = 2<p>
 * 输出：[4,5]<p>
 * 解释：以下为游戏进行情况：<p>
 * 1）第 1 个朋友接球，第 1 个朋友将球传给距离他顺时针方向 2 步的玩家 —— 第 3 个朋友。<p>
 * 2）第 3 个朋友将球传给距离他顺时针方向 4 步的玩家 —— 第 2 个朋友。<p>
 * 3）第 2 个朋友将球传给距离他顺时针方向 6 步的玩家 —— 第 3 个朋友。<p>
 * 4）第 3 个朋友接到两次球，游戏结束。<p>
 * <p>
 * 示例 2：<p>
 * 输入：n = 4, k = 4<p>
 * 输出：[2,3,4]<p>
 * 解释：以下为游戏进行情况：<p>
 * 1）第 1 个朋友接球，第 1 个朋友将球传给距离他顺时针方向 4 步的玩家 —— 第 1 个朋友。<p>
 * 2）第 1 个朋友接到两次球，游戏结束。<p>
 * <p>
 * 提示：<p>
 * 1 <= k <= n <= 50<p>
 */
public class LeetCode2682 {

    @Test
    public void test01() {
//        int n = 5, k = 2;
        int n = 4, k = 4;
        System.out.println(Arrays.toString(new Solution().circularGameLosers(n, k)));
    }
}

class Solution {
    public int[] circularGameLosers(int n, int k) {
        int[] ints = new int[n];
        List<Integer> list = new ArrayList<>();
        int pre = 0;
        ints[pre] = 1;
        int index = 1;
        while (true) {
            pre = (pre + index * k) % n;
            index++;
            ints[pre]++;
            // 存在有人第二次接到球时，结束循环
            if (ints[pre] > 1) {
                break;
            }
        }
        for (int i = 1; i < n; i++) {
            if (ints[i] == 0) {
                list.add(i + 1);
            }
        }
        return list.stream().mapToInt(Integer::intValue).toArray();
    }
}
